#!/usr/bin/env python3

"""
Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position
of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).
if the target is not found in the array, return [-1, -1]
"""

class Solution:
    def search_range(self, nums, target):
        if len(nums) == 0:
            return [-1, -1]

        left = self._search_position(True, nums, target, 0, len(nums) - 1)
        if left == -1:
            return [-1, -1]
        right = self._search_position(False, nums, target, 0, len(nums) - 1)
        return [left, right]

    def _search_position(self, is_left, nums, target, start, end):
        start_val = nums[start]
        end_val = nums[end]
        if end == start:
            return start if start_val == target else -1
        if start_val > target or target > end_val:
            return -1
        middle = int((start + end) / 2)
        if middle == start:
            if is_left:
                if start_val == target:
                    return start
                else:
                    return end if end_val == target else -1
            else:
                if end_val == target:
                    return end
                else:
                    return start if start_val == target else -1
        middle_val = nums[middle]
        if middle_val < target or (middle_val == target and not is_left):
            return self._search_position(is_left, nums, target, middle, end)
        else:
            return self._search_position(is_left, nums, target, start, middle)

if __name__ == '__main__':
    solution = Solution()
    result = solution.search_range([1], 0)
    print(str(result))
#    assert [3, 4] == solution.search_range([5, 7, 7, 8, 8, 10], 8)
#    assert [-1, -1] == solution.search_range([5, 7, 7, 8, 8, 10], 6)
